﻿using System;
using System.Linq;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Neighbours = Timtopia.DGMLPosterView.PowerGraphDecomposition.Neighbours<int>;
using Timtopia.PowerGraphBeamSearch;
using Microsoft.VisualStudio.GraphModel;
using Timtopia.DGMLPosterView;
using System.IO;
using System.Text.RegularExpressions;
using System.Diagnostics;

namespace PowerGraphBeamSearchTests
{
    [TestClass]
    public class PowerGraphBeamSearchTests
    {
        [TestInitialize]
        public void Initialize()
        {
        
            Modules.EdgeWeight = 1;
            Modules.CrossingWeight = 100;
            Modules.ModuleWeight = 10000;
        }

        [TestMethod]
        public void ModulesTest()
        {
            var m = GraphWithFiveNodes();
            Assert.AreEqual(ExpectedCost(edges: 7, modules: 0), m.Cost);

            var m2 = new Modules(m, m.GetModule(0), m.GetModule(1));
            Assert.AreEqual(ExpectedCost(7, 0), m.Cost);
            Assert.AreEqual(ExpectedCost(4, 1), m2.Cost);
            Assert.AreEqual(1, m2.GetModule(2).Incoming.Count);

            var m3 = new Modules(m2, m2.GetModule(2), m2.GetModule(3));
            Assert.AreEqual(ExpectedCost(4, 1), m2.Cost);
            Assert.AreEqual(ExpectedCost(3, 2), m3.Cost);

            var m4 = new Modules(m3, m3.GetModule(2), m3.GetModule(4));
            Assert.AreEqual(ExpectedCost(3, 2), m3.Cost);
            Assert.AreEqual(ExpectedCost(2, 2), m4.Cost);

            var m5 = new Modules(m3, m3.GetModule(0), m3.GetModule(2));
            Assert.AreEqual(ExpectedCost(3, 2), m3.Cost);
            Assert.AreEqual(ExpectedCost(edges: 3, modules: 3, crossings: 1), m5.Cost);

            var allEdges = m5.GetFlatGraph();
            Assert.AreEqual(ExpectedCost(edges: 7, modules: 0), allEdges.Count());
        }

        [TestMethod]
        public void ModuleTraversalTest()
        {
            var m = Merge(Merge(GraphWithFiveNodes(), 0, 1), 2, 3);
            Assert.AreEqual(ExpectedCost(edges: 3, modules: 2), m.Cost);
            m.InitializeMergeTraversal();
            var p = m.GetNextMergePair();
            Assert.IsTrue(SetEquals(p.Item1, 3, 2));
            Assert.IsTrue(SetEquals(p.Item2, 4));
            p = m.GetNextMergePair();
            Assert.IsTrue(SetEquals(p.Item1, 3, 2));
            Assert.IsTrue(SetEquals(p.Item2, 0, 1));
            p = m.GetNextMergePair();
            Assert.IsTrue(SetEquals(p.Item1, 4));
            Assert.IsTrue(SetEquals(p.Item2, 0, 1));
            Assert.IsNull(m.GetNextMergePair());
            // merge on top level modules only.
            //p = m.GetNextMergePair();
            //Assert.IsTrue(SetEquals(p.Item1, 3));
            //Assert.IsTrue(SetEquals(p.Item2, 2));
            //p = m.GetNextMergePair();
            //Assert.IsTrue(SetEquals(p.Item1, 0));
            //Assert.IsTrue(SetEquals(p.Item2, 1));
            //Assert.IsNull(m.GetNextMergePair());
        }

        [TestMethod]
        public void RealGraphTest()
        {
            var graph = Graph.Load(@"C:\Users\timd\Documents\Visual Studio 2012\CodePlexProjects\QuickGraph\3.0\sources\QuickGraph112Nodes.dgml");
            Assert.AreEqual(112, graph.Nodes.Count);
        }

        private void CheckEdges(ISet<Tuple<int, int>> edgeLookup, IEnumerable<Tuple<int, int>> edges)
        {
            int count = 0;
            foreach (var e in edges)
            {
                Assert.IsTrue(edgeLookup.Contains(e));
                count++;
            }
            Assert.AreEqual(edgeLookup.Count, count);
        }
        [TestMethod]
        public void RealGraphTest0()
        {
            var m0 = GraphWithFiveNodes();
            var edgeLookup = new HashSet<Tuple<int, int>>(m0.GetFlatGraph());
            var bs = new BeamSearch(m0, 10);
            Modules.CrossingWeight = 1000;
            Modules.EdgeWeight = 1000;
            Modules.ModuleWeight = 1;
            while (bs.Improve())
            {
                foreach (var m in bs.Beam)
                {
                    CheckEdges(edgeLookup, m.GetFlatGraph());
                }
            }
            foreach (var p in bs.Beam)
            {
                Console.WriteLine(p.Cost + p.ToString());
            }
            Assert.AreEqual(ExpectedCost(edges: 2, modules: 2), bs.Best.Cost);
            //bs.Best.WriteGraphML("RealGraphTest0.graphml", labelMap);
        }

        [TestMethod]
        public void RealGraphTest1()
        {
            Modules.CrossingWeight = 1;
            Modules.EdgeWeight = 1000;
            Modules.ModuleWeight = 1;
            var m0 = GraphWithSevenNodes();
            var edgeLookup = new HashSet<Tuple<int, int>>(m0.GetFlatGraph());
            var bs = new BeamSearch(m0, 100);
            while (bs.Improve())
            {
                foreach (var m in bs.Beam)
                {
                    CheckEdges(edgeLookup, m.GetFlatGraph());
                }
            }
            foreach (var p in bs.Beam)
            {
                Console.WriteLine(p.Cost + p.ToString());
            }
            //Assert.AreEqual(ExpectedCost(edges: 7, modules: 6), bs.Best.Cost);
            GraphMLWriter.WriteFile(bs.Best, "RealGraphTest1.graphml");
        }

        [TestMethod]
        public void PowerLawGraphsBeamSearch()
        {
            string[] files = Directory.GetFiles(@"..\..\ReferenceGraphs\powerlaw-generated-dzn\", "*out*");
            Assert.AreEqual(60, files.Count());

            foreach (var f in files)
            {
                var fileNameExpression = new Regex(@"graph-(\d\d).out-(\d+)-(\d+)");
                Assert.IsTrue(fileNameExpression.IsMatch(f));
                var m = fileNameExpression.Match(f);
                var graphNumber = m.Groups[1];
                var edgeWeight = int.Parse(m.Groups[2].ToString());
                var crossingWeight = int.Parse(m.Groups[3].ToString());

                // normalize crossing weight such that edge weight is fixed at 1000
                crossingWeight *= 1000 / edgeWeight;
                edgeWeight = 1000;

                //GetDecompositionStats(f, graphNumber, edgeWeight, crossingWeight);
                Console.Write("Graph" + graphNumber + ", ");
                DoBeamSearch(f, edgeWeight, crossingWeight, 1);
            }
        }

        [TestMethod]
        [Ignore]
        public void LargeGraphBeamSearch()
        {
            var f = @"..\..\ReferenceGraphs\JsonTextWriter.dgml";
            var graph = Graph.Load(f);
            Assert.AreEqual(140, graph.Nodes.Count);
            DoBeamSearch(graph, 1000, 500, 1, 1);
            //UnitTests.PowerGraphHeuristicVersusOptimalTests.GetDecompositionStats(graph, f, 1000, 500, 0);
        }

        [TestMethod]
        public void LargeGraphBeamSearch2()
        {
            var f = @"..\..\ReferenceGraphs\100-vertices\100-graph.dot";
            var graph = DotGraph.Load(f);
            Assert.AreEqual(100, graph.Nodes.Count);
            Assert.AreEqual(1594, graph.Links.Count);
            DoBeamSearch(graph, 1000, 0, 1, 1);
            UnitTests.PowerGraphHeuristicVersusOptimalTests.GetDecompositionStats(graph, f, 1000, 0, 0);
        }

        [TestMethod]
        public void GreedySearch1()
        {
            var f = @"..\..\ReferenceGraphs\100-vertices\100-graph.dot";
            var graph = DotGraph.Load(f);

            DoGreedySearch(graph);
        }

        private static void DoGreedySearch(Graph graph)
        {
            List<Tuple<string, string>> idAndLabelList;
            var ms = MakeModules(graph, 1000, 0, 1, out idAndLabelList);
            var search = new GreedyMerge(ms);
            Stopwatch sw = new Stopwatch();
            sw.Start();
            while (true)
            {
                bool improved = search.Improve();
                if (!improved) break;
            }
            Console.WriteLine("V = {0}, Cost = {1}, ElapsedTime = {2}", graph.Nodes.Count, ms.Cost, sw.ElapsedMilliseconds);
        }


        [TestMethod]
        public void GreedySearch2()
        {
            int[] vs = { 20 }; //{ 20, 30, 40, 50, 60, 70, 80, 90, 100 };
            foreach (var v in vs)
            {
                var f = @"..\..\ReferenceGraphs\100-vertices\" + v + "-graph.dot";
                var graph = DotGraph.Load(f);
                DoGreedySearch(graph);
                UnitTests.PowerGraphHeuristicVersusOptimalTests.GetDecompositionStats(graph, f, 1000, 0, 0);
            }
        }

        [TestMethod]
        public void LargeGraphBeamSearch3()
        {
            int[] vs = { 20, 30, 40, 50, 60, 70, 80, 90, 100 };
            int[] cw = { 0 }; //{ 1, 500, 2000 };
            int[] bs = { 5 }; //{ 1, 10, 100 };
            foreach (var v in vs)
            {
                var f = @"..\..\ReferenceGraphs\100-vertices\"+v+"-graph.dot";
                foreach (var c in cw)
                {
                    var graph = DotGraph.Load(f);
                    foreach (var b in bs)
                    {
                        DoBeamSearch(graph, 1000, c, 1, b);
                    }
                    //UnitTests.PowerGraphHeuristicVersusOptimalTests.GetDecompositionStats(graph, f, 1000, c, 0);
                }
            }
        }

        public void DoBeamSearch(string f, int edgeWeight, int crossingWeight, int moduleWeight, int beamSize = 10)
        {
            Graph g = PowerGraphDecomposition.LoadSimpleDescription(f, originalEdges: true);
            DoBeamSearch(g, edgeWeight, crossingWeight, moduleWeight, beamSize);
        }

        public void DoBeamSearch(Graph g, int edgeWeight, int crossingWeight, int moduleWeight, int beamSize = 10)
        {
            List<Tuple<string, string>> idAndLabelList;
            Modules m0 = MakeModules(g, edgeWeight, crossingWeight, moduleWeight, out idAndLabelList);
            var bs = new BeamSearch(m0, beamSize);
            var sw = new Stopwatch();
            sw.Start();
            Console.WriteLine("Starting Beam Search...");
            while (bs.Improve())
            {
                var best = bs.Best;
                //Console.WriteLine("EdgeWeight={0}, CrossingWeight={1}, Cost={2}, Modules={3}, Edges={4}, Crossings={5}, BeamSize={6}, elapsed time={7} seconds", edgeWeight, crossingWeight, best.Cost, best.ModuleCount, best.EdgeCount, best.CrossingCount, beamSize, (double)(sw.ElapsedMilliseconds) / 1000.0);
                //foreach (var m in bs.Beam)
                //{
                //    CheckEdges(edgeLookup, m.GetFlatGraph());
                //}
            }
            //foreach (var p in bs.Beam)
            //{
            //    CheckEdges(edgeLookup, p.GetFlatGraph());
            //    Console.WriteLine(p.Cost + p.ToString());
            //}
            //Assert.AreEqual(7013, bs.Best.Cost);
            {
                var best = bs.Best;
                Console.WriteLine("final: EdgeWeight={0}, CrossingWeight={1}, Cost={2}, Modules={3}, Edges={4}, Crossings={5}, Time={6}", edgeWeight, crossingWeight, best.Cost, best.ModuleCount, best.EdgeCount, best.CrossingCount, sw.ElapsedMilliseconds);
                GraphMLWriter.WriteFile(best, "best.graphml", idAndLabelList);
            }
        }

        private static Modules MakeModules(Graph g, int edgeWeight, int crossingWeight, int moduleWeight, out List<Tuple<string, string>> idAndLabelList)
        {
            var nodeMap = new Dictionary<GraphNode, int>();
            idAndLabelList = new List<Tuple<string, string>>();
            foreach (var v in g.Nodes.Where(n => !n.IsGroup && n.Label != "RenderControl"))
            {
                nodeMap[v] = idAndLabelList.Count;
                idAndLabelList.Add(Tuple.Create(v.Id.ToString(), v.Label));
            }
            var edges = new List<Tuple<int, int>>();
            foreach (var l in g.Links)
            {
                edges.Add(Tuple.Create(nodeMap[l.Source], nodeMap[l.Target]));
            }
            var edgeLookup = new HashSet<Tuple<int, int>>(edges);
            Modules.CrossingWeight = crossingWeight;
            Modules.EdgeWeight = edgeWeight;
            Modules.ModuleWeight = moduleWeight;
            return new Modules(nodeMap.Count, edges.ToArray());
        }

        [TestMethod]
        public void PowerLawGraph17()
        {
            int[] crossingWeights = {0}; //{ 1, 500, 2000 };
            int[] beamSizes = { 10 };
            foreach (var w in crossingWeights)
            {
                foreach (var k in beamSizes)
                {
                    RunPowerLawGraph(w, k);
                }
            }
        }
        private void RunPowerLawGraph(int crossingWeight, int beamSize)
        {
            Modules.CrossingWeight = crossingWeight;
            Modules.EdgeWeight = 1000;
            Modules.ModuleWeight = 1;
            var fname = @"..\..\ReferenceGraphs\powerlaw-generated-dzn\graph-17.out-1000-1";
            Graph g = PowerGraphDecomposition.LoadSimpleDescription(fname, originalEdges: true);

            var nodeMap = new Dictionary<GraphNode, int>();
            var idAndLabelList = new List<Tuple<string, string>>();
            foreach (var v in g.Nodes.Where(n => !n.IsGroup && n.Label != "RenderControl"))
            {
                nodeMap[v] = idAndLabelList.Count;
                idAndLabelList.Add(Tuple.Create(v.Id.ToString(), v.Label));
            } 
            var edges = new List<Tuple<int, int>>();
            foreach (var l in g.Links)
            {
                edges.Add(Tuple.Create(nodeMap[l.Source], nodeMap[l.Target]));
            }
            var edgeLookup = new HashSet<Tuple<int, int>>(edges);

            var sw = new Stopwatch();
            sw.Start();
            var m0 = new Modules(nodeMap.Count, edges.ToArray());
            var bs = new BeamSearch(m0, beamSize);
            while (bs.Improve())
            {
                foreach (var m in bs.Beam)
                {
                    CheckEdges(edgeLookup, m.GetFlatGraph());
                }
            }
            foreach (var p in bs.Beam)
            {
                CheckEdges(edgeLookup, p.GetFlatGraph());
                //Console.WriteLine(p.Cost + p.ToString());
            }
            //Assert.AreEqual(7013, bs.Best.Cost);
            var best = bs.Best;
            Console.WriteLine("Best: Cost={0}, Modules={1}, Edges={2}, Crossings={3}, V={4}, E={5}, Beam={6}, CrossingWeight={7}, time={8}", best.Cost, best.ModuleCount, best.EdgeCount, best.CrossingCount, nodeMap.Count, edges.Count, beamSize, Modules.CrossingWeight, sw.ElapsedMilliseconds);
            GraphMLWriter.WriteFile(best, "PowerLaw4.graphml", idAndLabelList);

            UnitTests.PowerGraphHeuristicVersusOptimalTests.GetDecompositionStats(g, fname, Modules.EdgeWeight, crossingWeight, 0);
            GraphMLWriter.WriteFile(g, "heuristic.graphml");
        }

        private bool SetEquals(IEnumerable<int> actual, params int[] expected)
        {
            return new HashSet<int>(actual).SetEquals(expected);
        }

        private static Modules Merge(Modules m, int a, int b)
        {
            return new Modules(m, m.GetModule(a), m.GetModule(b));
        }

        private static Modules GraphWithFiveNodes()
        {
            return new Modules(5, new Tuple<int, int>[] {
                Tuple.Create(0, 2),
                Tuple.Create(0, 3),
                Tuple.Create(0, 4),
                Tuple.Create(1, 2),
                Tuple.Create(1, 3),
                Tuple.Create(1, 4),
                Tuple.Create(2, 3),
            });
        }
        private static Modules GraphWithSevenNodes()
        {
            return new Modules(7, new Tuple<int, int>[] {
                Tuple.Create(0, 1),
                Tuple.Create(0, 3),
                Tuple.Create(0, 4),
                Tuple.Create(0, 5),
                Tuple.Create(0, 6),
                Tuple.Create(1, 6),
                Tuple.Create(2, 0),
                Tuple.Create(2, 1),
                Tuple.Create(2, 3),
                Tuple.Create(2, 4),
                Tuple.Create(2, 5),
                Tuple.Create(2, 6),
                Tuple.Create(3, 6),
                Tuple.Create(4, 1),
                Tuple.Create(4, 2),
                Tuple.Create(4, 3),
                Tuple.Create(4, 5),
                Tuple.Create(4, 6),
                Tuple.Create(5, 0),
                Tuple.Create(5, 2),
                Tuple.Create(5, 4),
                Tuple.Create(6, 1),
                Tuple.Create(6, 3),
            });
        }

        private int ExpectedCost(int edges, int modules, int crossings = 0)
        {
            return edges * Modules.EdgeWeight + modules * Modules.ModuleWeight + crossings * Modules.CrossingWeight;
        }
    }
}
